#include <iostream>

typedef char char_t;

int compute_LCS( char_t* A, char_t* B )
{
  int m = strlen(A) + 1;
  int n = strlen(B) + 1;

  // init c[m][n]
  int **c = new int*[m];
  c[0] = new int[m*n];
  for( int i = 1; i < m; i++ ){
    c[i] = c[i-1] + n;
  }

  for( int i = 0; i < m; i++ )
    c[i][0] = 0;

  for( int i = 0; i < n; i++ )
    c[0][i] = 0;

  for( int i = 1; i < m; i++ )
    for( int j = 1; j < n; j++ ) {
      if( A[i-1] == B[j-1] ){
        c[i][j] = c[i-1][j-1] + 1;
      } else if ( c[i-1][j] > c[i][j-1] ) {
        c[i][j] = c[i-1][j];
      } else {
        c[i][j] = c[i][j-1];
      }
    }

  for( int i = 0; i < m; i++ ) {
    for( int j = 0; j < n; j++ ) {
      ::std::cout << c[i][j] << "\t";
    }
    ::std::cout << "\n";
  }
  
  
  int result = c[m-1][n-1];
  
  delete[] c[0];
  delete[] c;

  return result;
}


int main()
{
  ::std::cout << compute_LCS( "ABCBDAB", "BDCABA" ) << ::std::endl;

  return 1;
}
